"""
=================================================
@coding ：UTF-8
@Project -> File   ：GraphTheory -> StandardTraverse.py
@Date   ：2024/6/12 14:00
@Author ：lzz
@Desc   ：Standard Traverse
==================================================
"""
import collections
import queue
from collections import deque
from typing import List


class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        """
        find the number of connected components in the graph
        :param isConnected: Adjacency matrix of the graph
        :return: the number of connected components in the graph
        """
        cities = len(isConnected)
        parent = list(range(cities))

        def find(index: int) -> int:
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]

        def union(index1: int, index2: int):
            parent[find(index1)] = find(index2)

        for i in range(cities):
            for j in range(i + 1, cities):
                if isConnected[i][j] == 1:
                    union(i, j)
        # sum函数对布尔值进行求和
        return sum(parent[i] == i for i in range(cities))

    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        """
        find eventual safe States
        A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting
        from that node leads to a terminal node (or another safe node).
        :param graph: a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i,
        meaning there is an edge from node i to each node in graph[i].
        :return: an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.
        """
        rg = [[] for _ in graph]
        for x, nodes in enumerate(graph):
            for y in nodes:
                rg[y].append(x)

        in_degree = [len(points) for points in graph]

        que = deque([i for i, length in enumerate(in_degree) if length == 0])

        while que:
            for y in rg[que.popleft()]:
                in_degree[y] -= 1
                if in_degree[y] == 0:
                    que.append(y)

        return [i for i, val in enumerate(in_degree) if val == 0]


    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        num = 0
        visited = {0}
        queue = deque([0])

        while queue:
            x = queue.popleft()
            num += 1

            for y in rooms[x]:
                if y not in visited:
                    visited.add(y)
                    queue.append(y)

        return num == len(rooms)

    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(n)]
        for x, y in redEdges:
            graph[x].append((0, y))
        for x, y in blueEdges:
            graph[x].append((1, y))

        dist = [-1] * n
        queue = [(1, 0), (0, 0)]
        visited = [(1, 0), (0, 0)]
        level = 0

        while queue:
            temp = queue
            queue = []
            for color, start_node in temp:
                if dist[start_node] == -1:
                    dist[start_node] = level
                for edge in graph[start_node]:
                    if edge[0] != color and edge not in visited:
                        queue.append(edge)
                        visited.append(edge)
            level += 1
        return dist



    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = collections.defaultdict(list)
        for i in range(n):
            graph[manager[i]].append(i)

        que = queue.Queue()
        que.put((headID, 0))
        res = 0

        while not que.empty():
            employee_id, time = que.get()

            if len(graph[employee_id]) > 0:
                for sub in graph[employee_id]:
                    que.put((sub, time + informTime[employee_id]))
            else:
                res = max(res, time)

        return res



    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]

        for edge in connections:
            graph[edge[0]].append((edge[1], 1))
            graph[edge[1]].append((edge[0], 0))

        def dfs(cur, parent) -> int:
            res = 0

            for edge in graph[cur]:
                if edge[0] == parent:
                    continue

                res += edge[1] + dfs(edge[0], cur)

            return res

        return dfs(0, -1)


    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        paths = list()
        stk = list()
        target = len(graph) - 1
        def dfs(x):
            if x == target:
                paths.append(stk[:])
                return
            for y in graph[x]:
                stk.append(y)
                dfs(y)
                stk.pop()

        stk.append(0)
        dfs(0)
        return paths

    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph = [[] for _ in range(n)]
        for x, y in connections:
            graph[x].append(y)
            graph[y].append(x)

        low = [0] * n
        time = [0] * n
        idx = [0]
        ans = []

        def dfs(cur: int, parent: int):
            idx[0] += 1
            low[cur] = time[cur] = idx[0]
            for child in graph[cur]:
                if time[child] == 0:
                    dfs(child, cur)
                    low[cur] = min(low[cur], low[child])
                    if low[child] > time[cur]:
                        ans.append([cur, child])
                elif time[child] < time[cur] and child != parent:
                    low[cur] = min(low[cur], time[child])

        dfs(0, -1)
        return ans

